﻿// 1009train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <set>

using namespace std;

/*
 屏幕给出 1 ~ 9 中任意 4 个不重复的数字
 - 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接，
 且屏幕不能同时给出 2 和 5；
 - 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接，
且屏幕不能同时给出 6 和 9

输入描述
输入以逗号分隔的 4 个 int 类型整数的字符串。

输出描述
输出为这几个数字可拼成的数字从小到大排列位于第 N （N为输入数字中最大的数字）位置的数字
如果输入的数字不在范围内或者有重复，则输出-1

输入
1,4,8,7
输出
41

1，4，7，8，14，17，18，41，47，48，71，74，78
 */
class Solution01
{
public:
    void backTrack(vector<int>& num_vec, vector<bool>&checked)
    {
        if (!track_v.empty())
        {
            string num_str;
            for (auto& num : track_v)
            {
                num_str += to_string(num);
            }
            result_set.insert(stoi(num_str));
        }
        if (track_v.size() == num_vec.size()) return;

        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            if (checked[i]) continue;
            checked[i] = true;
            track_v.push_back(num_vec[i]);
            backTrack(num_vec, checked);
            checked[i] = false;
            track_v.pop_back();
        }
	    //
    }
    void getTotal(vector<int>& curr_v, int index)
    {
        if (index==(int)replace_pos.size())
        {
            total_vec.push_back(curr_v);
            return;
        }
        int pos = replace_pos[index];

        vector<int>choose_v;
        choose_v.push_back(curr_v[pos]);
        choose_v.push_back(link_map.at(curr_v[pos]));
        
        int choose_size = choose_v.size();
        for (int i=0; i<choose_size; i++)
        {
            curr_v[pos] = choose_v[i];
            getTotal(curr_v, index + 1);
        }

	    //---
    }

    bool checkVerify(vector<int>& origin_v)
    {
	    //输入的数字不在范围内或者有重复，则输出-1
        unordered_set<int>repeat_set;

        for (auto&num:origin_v)
        {
            //1 ~ 9
            bool is_num = num >= 1 && num <= 9;
            if (!is_num) return false;
            if (repeat_set.count(num) > 0) return false;

            if (link_map.count(num)>0)
            {
                int link_num = link_map.at(num);
                if (repeat_set.count(link_num) > 0) return false;
            }

            repeat_set.insert(num);
        }
        return  true;
        //
    }

	Solution01(vector<int>&origin_v)
    {
        if (!checkVerify(origin_v))
        {
            cout << -1;
            return;
        }

        sort(origin_v.begin(), origin_v.end());
        int v_size = origin_v.size();
        for (int i=0; i<v_size; i++)
        {
            int curr = origin_v[i];
            if (link_map.count(curr)>0)
            {
                replace_pos.push_back(i);
            }
        }
        if (!replace_pos.empty())
        {
            vector<int>curr_v = origin_v;
            getTotal(curr_v, 0);
        }
        else
        {
            total_vec.push_back(origin_v);
        }

        int N = *max_element(origin_v.begin(), origin_v.end());
        for (auto&num_vec:total_vec)
        {
            vector<bool>checked(v_size, false);
            backTrack(num_vec, checked);
        }

        vector<int>result;
        for (auto&num:result_set)
        {
            result.push_back(num);
        }

        if (N>(int)result.size())
        {
            cout << -1;
            return;
        }
        cout << result[N-1];
	    //solu
    }
private:
    vector<int>track_v;
    set<int>result_set;
    vector<int>replace_pos;
    vector<vector<int>>total_vec;
    unordered_map<int, int>link_map = {
		{2,5},{5,2},{6,9},{9,6}
    };
};


/*
在每轮里选手可以选择获取该轮牌面，
则其总分数加上该轮牌面分数，为其新的总分数。
选手也可不选择本轮牌面直接跳到下一轮，此时将当前总分数还原为3轮前的总分数，
若当前轮次小于等于3（即在第1、2、3轮选择跳过轮次），则总分数置为0。
选手的初始总分数为0，且必须依次参加每一轮

输入描述
第一行为一个小写逗号分割的字符串，表示n轮的牌面分数，1 <= n <= 20。
分数值为整数，-100 <= 分数值 <= 100。
不考虑格式问题。

输出描述
所有轮结束后选手获得的最高总分数。

输入
1,-5,-6,4,3,6,-2
输出
11
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        vector<int>dynamic_v(v_size);

        //前三轮
        dynamic_v[0] = max(0, num_vec[0]);
        for (int i=1; i<3; i++)
        {
            int curr = dynamic_v[i - 1] + num_vec[i];
            dynamic_v[i] = max(0, curr);
        }

        for (int i=3; i<v_size; i++)
        {
            int curr = dynamic_v[i - 1] + num_vec[i];
            int prev = dynamic_v[i - 3];
            dynamic_v[i] = max(prev, curr);
        }

        cout << dynamic_v[v_size - 1];
	    //
    }
};

/*
从n个数中选若干（至少1）个数求和，求所有方案中第k小的和
输入
5 12
1 2 3 5 8
输出
8

说明
前12小的和分别为: 1 2 3 3 4 5 5 6 6 7 8 8
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec, int K)
    {
        int total_sum = accumulate(num_vec.begin(), num_vec.end(), 0);
        vector<int>dynamic_v(total_sum + 1);

        dynamic_v[0] = 1;

        for (auto&curr:num_vec)
        {
            for (int sum=total_sum; sum>0; sum--)
            {
                if (sum - curr < 0) continue;
                dynamic_v[sum] += dynamic_v[sum - curr];
            }
	        //
        }

        int count = 0;
        for (int sum=1; sum<=total_sum; sum++)
        {
            count += dynamic_v[sum];
            if (count>=K)
            {
                cout << sum;
                return;
            }
        }

	    //solu
    }
};


/*
输入描述
空格分割的两个字符串A与字符串B，字符串不为空串，
字符格式满足正则规则:[A-Z]，字符串长度<10000

输出描述
原点到终点的最短距离

输入
ABCABBA CBABAC
输出
9
 */
class Solution04
{
public:
    Solution04(string&str_x, string&str_y)
    {
        int col_size = str_x.size() + 1;
        int row_size = str_y.size() + 1;

        vector<vector<int>>dynamic_v(row_size, vector<int>(col_size));

        //从左到右
        for (int c=1; c<col_size; c++)
        {
            dynamic_v[0][c] = dynamic_v[0][c - 1] + 1;
        }

        //从上到下
        for (int r=1; r<row_size; r++)
        {
            dynamic_v[r][0] = dynamic_v[r - 1][0] + 1;
        }

        for (int r=1; r<row_size; r++)
        {
	        for (int c=1; c<col_size; c++)
	        {
                if (str_y[r-1]==str_x[c-1])
                {
                    dynamic_v[r][c] = dynamic_v[r - 1][c - 1] + 1;
                }
                else
                {
                    int prev_r = dynamic_v[r - 1][c];
                    int prev_c = dynamic_v[r][c - 1];

                    dynamic_v[r][c] = min(prev_r, prev_c) + 1;

                }
		        //for---
	        }
            //for--
        }

        cout << dynamic_v[row_size-1][col_size-1];
	    //Solu
    }
};


int main()
{
	{
        //ABCABBA CBABAC
        string str_x, str_y;
        cin >> str_x >> str_y;

        Solution04 solu(str_x, str_y);

        return 0;
	}
	{
        int v_size, K;
        cin >> v_size >> K;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }
        Solution03 solu(num_vec, K);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution02 solu(num_vec);

        return 0;
	}
    //vector<int>origin_v = { 1,2,8,6 };
    vector<int>origin_v;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (getline(oh_sstream, token, ','))
    {
        origin_v.push_back(stoi(token));
    }

    Solution01 solu(origin_v);
    return 0;
    //
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
